from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class BSTIterator:
    def __init__(self, root: Optional[TreeNode]):
        self.status = [[root, 'l']]


    def next(self) -> int:
        # print(self.status)
        if self.status[-1][1] == 'l':
            node = self.status[-1][0]
            if node.left:
                self.status.append([node.left, 'l'])
            else:
                self.status[-1][1] = 'm'
            return self.next()
        elif self.status[-1][1] == 'm':
            # print('m: ', self.status)
            self.status[-1][1] = 'r'
            return self.status[-1][0].val
        else:
            node = self.status[-1][0]
            if node.right:
                self.status.append([node.right, 'l'])
                return self.next()
            else:
                # 回退，直到不是r
                self.status.pop()
                # print('r:', self.status)
                while self.status[-1][1] == 'r':
                    self.status.pop()
                if self.status[-1][1] == 'l':
                    self.status[-1][1] = 'm'
                return self.next()


    def hasNext(self) -> bool:
        for s in self.status:
            if s[1] != 'r':
                return True
        node = self.status[-1][0]
        return node.right is not None



# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()


if __name__ == "__main__":
    root = TreeNode(7, TreeNode(3), TreeNode(15, TreeNode(9), TreeNode(20)))
    obj = BSTIterator(root)
    print(obj.next())
    print(obj.next())
    print(obj.hasNext())
    print(obj.next())
    print(obj.hasNext())
    print(obj.next())
    print(obj.hasNext())
    print(obj.next())
    print(obj.hasNext())
